package com.luoc.skipList;


import javafx.beans.binding.ObjectExpression;

import java.util.Random;

/**
 * @author luoc
 * @version 1.0
 * @date 2021/2/25 20:13
 * @since 1.0
 * 参考连接: https://www.cnblogs.com/buptleida/p/12838880.html
 */
public class SkipList<T extends Comparable<? super T>> {

    /** redis5 中最高层级6 4*/
    private int MAX_LEVEL = 64;

    /**头结点*/
    private SkipListNode<T> header;

    /**尾结点*/
    private SkipListNode<T> tail;

    /**记录跳跃表的长度 */
    private long length;

    /**记录目前跳跃表内，层数最大的那个节点的层数*/
    private int maxLevel ;

    /** 构造方法初始化SkipList */
    public SkipList() {
        this.header = new SkipListNode<T>(null);
        this.tail = new SkipListNode<T>(null);
        this.length = 0;
        this.maxLevel = 1;
    }

    /**获取随机高度层数*/
    private  int getRandomHeight() {
        Random random = new Random();
        int i = 1;
        for (; i < MAX_LEVEL; ++i) {
            if (random.nextInt(2) == 0) {
                break;
            }
        }
        return i;
    }


    /**
     *  新增节点
     *  随机层数高于目前跳跃表的层数， 所有高于 maxlevel 的 头结点都是 update[i]， 且rank[i]为0,
     * 1，查找要插入的位置,
     * 2，调整跳跃表的高度
     * 3，插入节点
     * 4，调整backward 回退指针
     * */
    public SkipListNode zslInsert(double score,T obj){
        int levelHeight = getRandomHeight();
        SkipListNode<T> target = new SkipListNode<T>(obj, levelHeight, score);
        // update[i]插入节点时，需要更新被插入节点每层的前一个节点。
        // 由于每层更新的节点不一样，所以将每层需要更新的节点记录在update[i]中
        SkipListNode[] update = new SkipListNode[Math.max(levelHeight, maxLevel)];
        // rank[i] 记录当前层从header节点到update[i]节点所经历的步长，
        // 在更新update[i]的span和设置新插入节点的span时用到
        int[] rank = new int[update.length];
        int i = update.length - 1;
        // levelHeight 大于 maxLevel 高的头结点都是修改的前节点
        if (levelHeight > maxLevel) {
            for (; i >= maxLevel; --i) {
                update[i] = header;
                rank[i] = 0;
            }
            maxLevel = levelHeight;
        }
        for (; i >= 0; --i) {
            SkipListNode<T> node = header;
            SkipListNode<T> next = node.getLevel()[i].getForward();
            rank[i] = 0;
            //遍历得到与target最接近的节点(左侧)
            while (next != null && (score > next.getScore()
                    || score == next.getScore() && next.getObj().compareTo(obj) < 0)) {
                rank[i] += node.getLevel()[i].getSpan();
                node = next;
                next = node.getLevel()[i].getForward();
            }
            update[i] = node;
        }

        //当maxLevel>levelHeight，前面部分节点的span值加1，因为该节点与forword指向节点之间将要 多出来一个新节点
        for (i = update.length - 1; i >= levelHeight; --i) {
            int span = update[i].getLevel()[i].getSpan();
            update[i].getLevel()[i].setSpan(++span);
        }
        //遍历 update[] 进行插入和更新操作
        for (; i >= 0; --i) {
            SkipListLevel pre = update[i].getLevel()[i];
            //将target节点插入update[i]和temp之间
            SkipListNode<T> temp = pre.getForward();
            int span = pre.getSpan();

            pre.setForward(target);
            pre.setSpan(rank[0] + 1 - rank[i]);

            target.getLevel()[i].setSpan(span > 0 ? (span - rank[0] + rank[i]) : 0);
            target.getLevel()[i].setForward(temp);
            //设置后退指针
            if (temp == null) {
                target.setBackward(header);
            } else {
                target.setBackward(temp.getBackward());
                temp.setBackward(target);
            }
        }

        if (tail.getLevel()[0].getForward() != null) {
            tail = target;
        }
        length++;
        return target;
    }

//    public SkipListNode<T> zsInsert(double score, Object object){
//        // 获取随机层数
//        int levelHeight = getRandomHeight();
//        // 新插入节点
//        SkipListNode target = new SkipListNode(object,levelHeight,score);
//        // update[i]插入节点时，需要更新被插入节点每层的前一个节点。
//        // 由于每层更新的节点不一样，所以将每层需要更新的节点记录在update[i]中
//        SkipListNode[] update = new SkipListNode[Math.max(levelHeight,maxLevel)];
//        // rank[i] 记录当前层从header节点到update[i]节点所经历的步长，
//        // 在更新update[i]的span和设置新插入节点的span时用到
//        int[] rank = new int[update.length];
//        // 当新的层数 levelHeight 大于 当前 maxlevel 时，高于的节点都是update[i]
//        int i=levelHeight;
//        for (; i >= maxLevel; --i){
//              update[i] = header;
//              rank[i] = 0;
//        }
//
//
//        for (; i>=0; --i){
//            //查找插入的节点
//            SkipListNode temp = header;
//            while (temp.getLevel()[i].getForward() !=null && temp.getScore() < target.getScore()){
//                   temp = header.getLevel()[i].getForward();
//                   rank[i] += temp.getLevel()[i].getSpan();
//            }
//            update[i] = temp;
//        }
//
//
//        //随机层数小于目前跳跃表的层数, 所有低于maxlevel的 update[i].getLevel()[i].getspan() +1, 因为中间要新插入一个接口
//        for (i = update.length - 1; i >= levelHeight; --i) {
//            int span = update[i].getLevel()[i].getSpan();
//            update[i].getLevel()[i].setSpan(++span);
//        }
//
//        for (; i>=0; --i){
//            SkipListLevel pre = update[i].getLevel()[i];
//            //将target节点插入update[i]和temp之间
//            SkipListNode<T> temp= pre.getForward();
//            int span = pre.getSpan();
//
//            pre.setSpan(rank[0] - rank[i] +1);
//            pre.setForward(target);
//
//            target.getLevel()[i].setForward(temp);
//            target.getLevel()[i].setSpan(span -  rank[0] + rank[i]);
//
//            // 设置后退指针
//            if (temp == null){
//                header = target;
//            }else {
//                target.setBackward(temp.getBackward());
//                temp.setBackward(target);
//            }
//
//            if (tail.getLevel()[0].getForward() != null) {
//                tail = target;
//            }
//            length++;
//            return target;
//        }

//        return null;
//    }

    /**
     * 删除节点
     * @param obj
     * @return 删除的节点(若节点不存在则返回null)
     */
    public SkipListNode zslDelete(double score, T obj) {
        SkipListNode[] update = new SkipListNode[maxLevel];
        SkipListNode<T> node = header;
        for (int i = maxLevel - 1; i >= 0; --i) {
            SkipListNode<T> next = node.getLevel()[i].getForward();
            //遍历得到与target最接近的节点
            while (next != null && (score > next.getScore() || score == next.getScore() && next.getObj().compareTo(obj) < 0)) {
                node = next;
                next = node.getLevel()[i].getForward();
            }
            update[i] = node;
        }
        //待删除的目标节点
        SkipListNode<T> target = update[0].getLevel()[0].getForward();
        if(target==null) return null;

        for (int i = maxLevel - 1; i >= 0; --i) {
            SkipListLevel current = update[i].getLevel()[i];
            SkipListNode<T> next = current.getForward();
            if (next == null) continue;
            if (next != target) {
                current.modifySpan(-1);
                continue;
            }
            current.setForward(target.getLevel()[i].getForward());
            if(current.getForward()!=null)
                current.modifySpan(target.getLevel()[i].getSpan() - 1);
            else
                current.setSpan(0);
        }
        length--;
        while(header.getLevel()[maxLevel-1].getSpan()==0){
            maxLevel--;
        }
        return target;
    }


//    public SkipListNode<T> zslFirstInRange(double fromScore, double toScore, SkipListNode<T> node, int k) {
//        if (!zslIsInRange(fromScore, toScore)) {
//            return null;
//        }
//
//        SkipListNode<T> next = node.getLevel()[k].getForward();
//
//        if (next == null || next.getScore() >= fromScore) {
//            if (k == 0) return next != null && next.getScore() > toScore ? null : next;
//            return zslFirstInRange(fromScore, toScore, node, k - 1);
//        }
//        return zslFirstInRange(fromScore, toScore, next, k);
//    }
//
//
//    public SkipListNode<T> zslLastInRange(double fromScore, double toScore, SkipListNode<T> node, int k) {
//        if (!zslIsInRange(fromScore, toScore)) {
//            return null;
//        }
//
//        SkipListNode<T> next = node.getLevel()[k].getForward();
//
//        if (next == null || next.getScore() > toScore) {
//            if (k == 0) return next != null && next.getScore() < fromScore ? null : node;
//            return zslLastInRange(fromScore, toScore, node, k - 1);
//        }
//        return zslLastInRange(fromScore, toScore, next, k);
//    }

//    public static void main(String[] args) {
//        int i =2;
//        System.out.println(++i);
//    }

}
